package leecode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode24 {
    public int cuttingRope(int n) {
        if(n<=2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        int count=0;
        if(n%3==0){
            count=n/3;
            return (int) Math.pow(3,count);
        }
        if(n%3==1){
            count=n/3;
            return (int) (Math.pow(3,count-1)*4);
        }
        if(n%3==2){
            count=n/3;
            return (int) Math.max(Math.pow(3,count)*2,Math.pow(3,count-1)*5);
        }
        return 0;
    }
    //第2题
    public int[][] findContinuousSequence(int target) {
        int sum=0;
        List<int []>list=new ArrayList<>();
        for (int i = 1,j= 1; j < target; j++) {
            sum+=j;
            while (sum>target){
                sum-=i;
                i++;
            }
            if(sum==target){
                int[]arr=new int[j-i+1];
                for (int k=0;k<j-i+1;k++){
                    arr[k]=i+k;
                }
                list.add(arr);
            }
        }
        int[][]num=new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            num[i]=list.get(i);
        }
        return num;
    }
    //第三题
    /**
    思路：使用数学方法(先举例)
            你要知道最后的结果是3，带着结果去看问题

        第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
        (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
        第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
        第三次，【1, 3, 4】，本轮要踢出4                                        看1
        第四次，【1, 3】 本轮要踢出1                                            看3
        第五次，【3】
        最后返回3

        我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
        你从第二次，向上看第一次
        你会发现，原来3在0的位置
                现在，3在(0 + 3) % 5
                        => +3 回到上次的位置
                        => %5 防止数组溢出，并且数组本来就是循环数组

        f(n) = ( f(n - 1) + m ) % n
        解释意思：
            f(n) 表示上一次
            f(n - 1) 表示这次，因为我们要从这次回推上一次
            m 表示隔几个
            n表示上一次的数组长度

     */
    public int lastRemaining(int n, int m) {
        int res = 0;// 最后只剩下一位，坐标肯定是0
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}
